const { buildBinaryTree, consoleTree } = require('../tools');

// 前序遍历
// 递归
const preOrderTraversal = (node) => {
  if (!node) return [];
  const ans = [node.val];
  ans.push(...preOrderTraversal(node.left));
  ans.push(...preOrderTraversal(node.right));
  return ans;
}
// 迭代
const preOrderTraversal_1 = (node) => {
  if (!node) return [];
  const ans = [];
  const stack = [node];
  while (stack.length > 0) {
    const cur = stack.pop();
    ans.push(cur.val);
    if (cur.right) stack.push(cur.right);
    if (cur.left) stack.push(cur.left);
  }
  return ans;
};


// 中序遍历
// 递归
const inOrderTraversal = (node) => {
  if (!node) return [];
  const ans = inOrderTraversal(node.left);
  ans.push(node.val);
  ans.push(...inOrderTraversal(node.right));
  return ans;
}
// 迭代
const inOrderTraversal_1 = (node) => {
  if (!node) return [];
  const ans = [];
  const stack = [];
  let cur = node;
  while (cur !== null || stack.length > 0) {
    while (cur !== null) {
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop();
    ans.push(cur.val);
    cur = cur.right;
  }
  return ans;
};
// Morris遍历
const inOrderTraversal_morris = (node) => {
  const ans = [];
  let cur = node;
  while (cur !== null) {
    if (cur.left !== null) {
      let p = cur.left;
      while (p.right !== null) {
        p = p.right;
      }
      p.right = cur;

      let old = cur;
      cur = cur.left;
      old.left = null;
    } else {
      ans.push(cur.val);
      cur = cur.right;
    }
  }
  return ans;
};

// 后序遍历
// 递归
const postOrderTraversal = (node) => {
  if (!node) return [];
  const ans = postOrderTraversal(node.left);
  ans.push(...postOrderTraversal(node.right));
  ans.push(node.val);
  return ans;
}
// 迭代
const postOrderTraversal_1 = (node) => {
  if (!node) return [];
  const stack = [];
  const ans = [];
  let lastVisit = null;
  let cur = node;

  while (cur !== null || stack.length > 0) {
    while (cur !== null) {
      stack.push(cur);
      cur = cur.left;
    }

    cur = stack[stack.length - 1];

    if (cur.right === null || cur.right === lastVisit) {
      stack.pop()
      ans.push(cur.val);
      lastVisit = cur;
      cur = null;
    } else {
      cur = cur.right;
    }
  }

  return ans;
};
// 迭代 双栈
const postOrderTraversal_2 = (node) => {
  if (!node) return [];
  const stack_1 = [node];
  const ans_1 = [];

  while (stack_1.length > 0) {
    const cur = stack_1.pop();
    ans_1.push(cur.val);
    if (cur.left) stack_1.push(cur.left);
    if (cur.right) stack_1.push(cur.right);
  }

  return ans_1.reverse();
};

// const tree = buildBinaryTree([1, 2, 3, 4, 5, 6, 7]);
// consoleTree(tree);
// const ans1_1 = preOrderTraversal(tree);
// const ans1_2 = preOrderTraversal_1(tree);
// console.log(ans1_1, ans1_2);
// const ans2_1 = inOrderTraversal(tree);
// const ans2_2 = inOrderTraversal_1(tree);
// console.log(ans2_1, ans2_2);
// const ans3_1 = postOrderTraversal(tree);
// const ans3_2 = postOrderTraversal_1(tree);
// const ans3_3 = postOrderTraversal_2(tree);
// console.log(ans3_1, ans3_3);